﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using psieve.sieve;

namespace psieve.factor
{
    public class Fermat : IFactor
    {
        struct Cycle
        {
            public int[] squares;
            public bool[] valid;

            public Cycle(BigInteger n, BigInteger a, int baze)
            {
                squares = new int[baze];
                bool[] valid0 = new bool[baze];
                valid = new bool[baze];

                for (int x = 0; x < baze; x++)
                {
                    BigInteger ax = a + x;
                    squares[x] = (int) ((ax * ax - n) % baze);
                    valid0[(x *(long) x)%baze] = true;
                }

                for (int x = 0; x < baze; x++)
                    valid[x] = valid0[squares[x]];
            }
        }

        class MultiCycle
        {
            private readonly bool[][] valids;
            private readonly int[][] offsets;

            private readonly int[] idx;
            private readonly int[] bases;

            public MultiCycle(BigInteger n, BigInteger a, int[] bases)
            {
                this.bases = bases;
                idx = new int[bases.Length];
                valids = new bool[bases.Length][];
                offsets = new int[bases.Length][];

                for (int x = 0; x < idx.Length; x++)
                {
                    Cycle c = new Cycle(n, a, bases[x]);
                    PrintStats(c);

                    valids[x] = c.valid;

                    var validList = c.valid.ToList();

                    offsets[x] = new int[validList.Count];

                    for (int y = 0; y < validList.Count; y++)
                    {
                        int next = validList.FindIndex(y, e => e);
                        offsets[x][y] = Math.Max(0, next - y);
                    }
                }
            }

            public int Advance()
            {
                int k2;
                int max;
                for (k2 = 0; k2 < 1000000; k2 += max)
                {
                    max = idx.Select((e, x) => offsets[x][e]).Max();

                    if (k2 == 0 && max == 0)
                        max = 1;

                    if (max == 0)
                    {
                        //Console.WriteLine("k2: " + k2);
                        return k2;
                    }

                    for (int x = 0; x < idx.Length; x++)
                        idx[x] = (idx[x] + max) % bases[x];
                }

                //for (int k = 1; k < 1000000; k++)
                //{
                //    bool valid = true;
                //    for (int x = 0; x < idx.Length; x++)
                //    {
                //        int y = (idx[x] + 1)%bases[x];
                //        idx[x] = y;
                //        valid &= valids[x][y];
                //    }

                //    if (valid)
                //        return k;
                //}

                throw new ApplicationException("no valid entries!");
            }
        }

        private static readonly long[] smallPrimes = new Eratosthenes().Sieve(1000).OrderBy(e => e).ToArray();

        private static void PrintStats(Cycle c)
        {
            Console.WriteLine("cycle size: " + c.valid.Length);
            int cnt = c.valid.Count(e => e);
            Console.WriteLine("possible hits: " + cnt + " (" + (cnt / (double)c.valid.Length) * 100.0 + "%)");            
        }

        private static void PrintStats(Cycle c1, Cycle c2)
        {
            if(c1.valid.Length > c2.valid.Length)
                PrintStats(c2, c1);
            else
            {
                Cycle joined = new Cycle{squares = new int[0], valid = new bool[c2.valid.Length]};

                for (int x = 0; x < joined.valid.Length; x++)
                {
                    joined.valid[x] = c1.valid[x % c1.valid.Length] && c2.valid[x];
                }

                PrintStats(joined);
            }
        }

        //2,3,5,7,11,13,17
        //19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97

        private static BigInteger Split(BigInteger num)
        {
            Console.WriteLine("splitting: " + num);

            BigInteger a = num.Sqrt() + 1;

            int base1 = 2*3*5*7*11*13*17;
            int base2 = 19*23*29*31;
            //int base3 = 37*41*43;
            int base3 = 4000 * 5;
            int base4 = 97 * 89 * 83;

            MultiCycle mc = new MultiCycle(num, a, new []{base1, base2, base3});

            for(int x = mc.Advance(); ; x = mc.Advance())
            {

                //BigInteger b2Temp = a * a - num;
                //Console.WriteLine("a: " + a + ", b2: " + b2Temp + ", a%m: " + a % baze + ", b2%m: " + b2Temp % baze);
                //Console.WriteLine(c3.squares[x] + ", " + c3.valid[x]);

                a += x;

                BigInteger b2 = a * a - num;
                BigInteger sqrt = b2.Sqrt();

                // prime
                if (a - sqrt < smallPrimes[smallPrimes.Length - 1])
                {
                    Console.WriteLine(num + " is prime");
                    return 1;
                }

                if (sqrt*sqrt == b2)
                {
                    Console.WriteLine("found a factor: " + (a - sqrt));
                    return a - sqrt;
                }
            }
        }

        public IEnumerable<BigInteger> Factor(BigInteger num)
        {
            // check some trivial cases
            foreach (long p in smallPrimes)
            {
                if (num == p)
                    return new List<BigInteger> {num};
                
                if(num % p == 0)
                    return new List<BigInteger> {p}.Concat(Factor(num/p));
            }

            // check for perfect square
            BigInteger sqrt = num.Sqrt();
            if (sqrt*sqrt == num)
            {
                List<BigInteger> fac = Factor(sqrt).ToList();
                return fac.Concat(fac);
            }

            BigInteger s = Split(num);
            if (s == 1)
                return new List<BigInteger> {num};

            BigInteger test = num/s;
            BigInteger test2 = test*s;

            if (test2 != num)
            {
                Console.WriteLine("num  : " + num);
                Console.WriteLine("s    : " + s);
                Console.WriteLine("test : " + test);
                Console.WriteLine("test2: " + test2);

                throw new ApplicationException("test2 != num: " + test2 + " vs " + num);
            }

            return Factor(s).Concat(Factor(num/s));
        }
    }
}
